home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / misc_pto / b-trees / btrees.txt
Text File  |  1990-01-08  |  9KB  |  186 lines
  1.  
  2.  
  3.                                  B-Trees
  4.  
  5.  
  6.                         SCSC 420 - File Management
  7.  
  8.                        University of South Carolina
  9.  
  10.                                J. E. Clary
  11.  
  12.  
  13.  
  14.  
  15.              The  concept of B-Trees grew from a  competition  by 
  16.          leading computer manufacturers and independent  research 
  17.          groups  in  the  late 1960's. This  competition  was  to 
  18.          develop general methods for storing and retrieving  data 
  19.          in large file systems that would provide rapid access to 
  20.          the  data  with  a  minimal  overhead  cost.  Among  the 
  21.          competitors  were  R. Bayer and E. McCreight,  who  were 
  22.          employees  of  the Boeing Corporation at  the  time.  In 
  23.          1972, Bayer and McCreight published an article  entitled 
  24.          "Organization and Maintenance of Large Ordered  Indexes" 
  25.          which  first exposed the world to the conception  of  B-
  26.          Tree organization. 
  27.  
  28.               The need for a new method to access data arose from 
  29.          the  long  seek times associated  with  ordinary  access 
  30.          methods and the need to have a sorted index in order  to 
  31.          perform  binary searches. The overhead of maintaining  a 
  32.          sorted index was deemed unacceptable so a new method was 
  33.          needed. 
  34.  
  35.              One  explored solution was to use binary tree.  This 
  36.          method would alleviate the need to resort the index with 
  37.          each new entry or deletion, but it too had some inherent 
  38.          problems.   Because  the  binary  tree  is  located   on 
  39.          secondary  storage,  the number of  seeks  necessary  to 
  40.          satisfy a search can be very high. A successful strategy 
  41.          for  this  is to reduce the seeks by  paging  groups  of 
  42.          nodes in and out of memory. 
  43.  
  44.              Another  difficulty with binary trees is  that  they 
  45.          are constructed starting with the root and working  down 
  46.          through  the nodes. After construction, it  is  possible 
  47.          that the tree root could contain the wrong keys,  making 
  48.          it  necessary  to find ways to repair the  problem  with 
  49.          rearrangement algorithms. Bayer and McCreight recognized 
  50.          that  the decision to construct the tree from  the  root 
  51.          down, was in itself the problem. Rather than find a  way 
  52.          to  undo  the problems inherent to  binary  trees,  they 
  53.          concentrated  on algorithms to construct the tree  in  a 
  54.          useful form to start with. With B-Trees the root node is 
  55.          allowed  to emerge, rather than setting it up, and  then 
  56.          perhaps having to change it. 
  57.  
  58.              Each  node  of  a  B-Tree  consists  of  an  ordered 
  59.          sequence  of  entries and some pointers. The  number  of 
  60.          pointers  is always equal to the number of entries +  1. 
  61.          The  maximum number of entries that can be stored  in  a 
  62.          node  is  called the order of the B-Tree.  When  a  node 
  63.          becomes full, it is split into two nodes and the entries 
  64.          evenly distributed between the old node and the new one. 
  65.          Since  we  now  have two nodes, there is a  need  for  a 
  66.          higher level in the tree to enable us to choose  between 
  67.          the two nodes when searching. This new node, in  essence 
  68.          will  become our new root node. When a new root node  is 
  69.          created,  it needs to contain an entry also. The  method 
  70.          to  accomplish this is to move the entry that  separates 
  71.          the two lower level nodes into the root. This is  called 
  72.          promoting the entry. 
  73.  
  74.               By using these methods to construct a tree, we  are 
  75.          assured that the tree is always in balance, with  regard 
  76.          to height. The path length from the root to any leaf  is 
  77.          the  same as the path length from the root to any  other 
  78.          leaf. Another positive aspect of this type  construction 
  79.          is  that the entries that are promoted, are the  entries 
  80.          that we want to be in the root node. By working up  from 
  81.          the  leaf level, splitting and promoting as  nodes  fill 
  82.          up, we eliminate the problems encountered with  ordinary 
  83.          binary trees. 
  84.  
  85.              Because  of the properties of a B-Tree, many of  the 
  86.          operations  on  the tree can be  done  recursively.  The 
  87.          simplest  of these operations is searching.  The  search 
  88.          through a B-Tree is divided into two distinctive  parts. 
  89.          First the node where the entry should reside is located. 
  90.          Then  the  node itself is searched  for  the  particular 
  91.          entry. 
  92.  
  93.              The next operation to be considered is insertion  of 
  94.          new data into the B-Tree. First, the Insertion algorithm 
  95.          must locate the node in which the new data item is to be 
  96.          placed.   Second,   the  algorithm  searches   for   the 
  97.          possibility  that  the data to be  inserted  is  already 
  98.          contained in the tree. If the data is not already in the 
  99.          tree,  the correct insertion point is located.  At  this 
  100.          point  the  insertion  is  made.  There  is  always  the 
  101.          possibility  that  the  node where the  data  is  to  be 
  102.          inserted may be full. If this is the case, the insertion 
  103.          algorithm  must  be able to control  the  promotion  and 
  104.          splitting of the node. Depending on the contents of  the 
  105.          B-Tree,  this  promotion  and splitting  may  filter  up 
  106.          through  the higher nodes and may even cause a new  root 
  107.          node to be created. 
  108.  
  109.                The process of splitting and promoting used in the 
  110.          insertion  algorithm ensures that the rules of a  B-Tree 
  111.          be  maintained. This is also the case for  the  deletion 
  112.          algorithm.  The  removal of an entry must occur  at  the 
  113.          leaf level. When the desired entry is located in a leaf, 
  114.          simply delete that entry. If the entry is not in a leaf, 
  115.          we  swap  the  entry with its  immediate  successor  and 
  116.          delete it then. 
  117.  
  118.              At times, the deletion of an entry will cause the B-
  119.          Tree to experience underflow. Underflow is the condition 
  120.          where  the number of entries in a leaf is less than  the 
  121.          minimum number of entries allowed by that order  B-Tree. 
  122.          When underflow occurs, the first thing to do is to  look 
  123.          at  the  left sibling. If it has more than  the  minimum 
  124.          number  of entries allowed, redistribute the both  nodes 
  125.          entries  so that they each contain at least the  minimum 
  126.          entries  allowed. If neither sibling has more  than  the 
  127.          minimum, concatenate the two leaves and along with their 
  128.          median  entry from the parent node into one  leaf.  When 
  129.          concatenation occurs, you must check the parent to  make 
  130.          sure it does not underflow. 
  131.  
  132.              Another condition that can occur during deletion  is 
  133.          when  the root experiences undeflow. When  this  happens 
  134.          the  remaining entry in the root is absorbed into a  new 
  135.          root. This in turn causes the height of the B-Tree to be 
  136.          decreased. 
  137.  
  138.              These   are   just   the   essentials   of    B-Tree 
  139.          implementation.   Over   the  years  since   Bayer   and 
  140.          McCreight, the concept of the B-Tree has evolved into  a 
  141.          more  efficient entities. One derivative, B*-Trees  uses 
  142.          enhanced splitting and redistribution processes so as to 
  143.          increase  the  storage  utilization. Others  go  a  step 
  144.          further  and create Virtual B-Trees. Reguardless of  the 
  145.          implementation,  the  B-Tree as proposed  by  Bayer  and 
  146.          McCreight  has become the de facto standard for  indexes 
  147.          into a data base system. 
  148.          
  149.          Sources: 
  150.  
  151.  
  152.          File and Database Techniques,
  153.  
  154.             James Bradley,
  155.             University of Calgary
  156.  
  157.  
  158.          File Design & Programming,
  159.  
  160.             W.  Wesley Peterson and Art Lew,
  161.             University of Hawaii at Manoa
  162.  
  163.  
  164.          File Management Techniques,
  165.  
  166.             Billy G. Claybrook,
  167.             The MITRE Corporation
  168.  
  169.  
  170.          File Structures,
  171.  
  172.             Michael J. Folik and Bill Zoellick,
  173.             Oklahoma State University
  174.  
  175.  
  176.          Pascal plus Data Structures,
  177.  
  178.             Nell Dale,
  179.             University of Texas as Austin
  180.  
  181.  
  182.          Understanding Data Base Management Systems,
  183.  
  184.             Joseph A. Vasta,
  185.             Bethlehem Steel Corporation
  186.